import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author 03010570
 * @date 2020/07/09
 * describe:    LeetCode : 面试题 17.13 、恢复空格  https://leetcode-cn.com/problems/re-space-lcci/
 */
public class LeetCode_interview_17_13 {

    public static void main(String[] args) {
        String[] dict =new String[]{"abcd", "ab", "def"};
        String sentence = "abcdef";
        System.out.println(respace(dict,sentence));
    }

    public static int respace(String[] dictionary, String sentence) {
        Set<String> dict = new HashSet<>(Arrays.asList(dictionary));
        int n = sentence.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int idx = 0; idx < i; idx++) {
                if (dict.contains(sentence.substring(idx, i))) {
                    dp[i] = Math.min(dp[i], dp[idx]);
                }
            }
        }
        return dp[n];
    }

}
